package com.yangli.leecode.mashib.interview;

/**
 * @Description 最长递增子序列长度
 * @Author liyang
 * @Date 2023/2/9 11:10
 */
public class Seventeen {
    public static void main(String[] args){
        Seventeen seventeen = new Seventeen();

        System.out.println(seventeen.maxIncrementSub(new int[]{4, 1, 3, 2, 3, 9, 5, 6}));
        //System.out.println(seventeen.findOriginal(753));
    }

    //O(n^2)
    public int maxIncrementSub(int[] arr){
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int[] dp = new int[arr.length];
        int res = 0;
        for (int i = 0; i < arr.length; i++) {
            dp[i] = 1;
            if (i != 0) {
                for (int j = i - 1; j >= 0; j--) {
                    if (arr[i] > arr[j]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;

    }

    //O(n*logn)
    public int maxIncrementSub2(int[] arr){
        if (arr == null || arr.length == 0) {
            return 0;
        }

        int[] end = new int[arr.length];//记录当前所有i+1长度子序列的最小数
        int res = 0;
        for (int i = 0; i < arr.length; i++) {
            int l = 0;
            int r = arr.length - 1;

            while (l <= r) {
                int mid = (l + (r - l) >> 1);
                if (end[mid] == arr[i]) {
                    break;
                }
                if (arr[i] > end[mid]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            r = Math.max(r, l);//==>要替换的位置，这样操作之后会有两种情况，例如arr[i]=6;r2=5 l3=7==>  r2=5 l2=5(l3为0) 如果有3尽量选3，如果没3就说明相等都等于2
            end[r] = arr[i];
            res = Math.max(res, i + 1);
        }
        return res;

    }

}
